package 剑指Offer.简单;

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: [0,1,3]
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/8/28 10:12
 */
public class _53II0到n减一中缺失的数字 {

    /**
     * 普通遍历查找 从第一位开始，如果位数不为预期的count则返回
     */
    public int missingNumber(int[] nums) {
        int count = 0;
        for (int num : nums) {
            if (num != count) {
                return count;
            }
            count++;
        }
        return count;
    }

    /**
     * 前提：因为数组本身是有序的，面对有序数组中的搜索问题优先采用二分查找法
     * 跳脱的条件是当前的值不等于当前的下标 数组是从0~n-1的数字
     */
    public int missingNumberV2(int[] nums) {
        int left = 0, right = nums.length;
        while(left <= right) {
            int m = (left + right) / 2;
            if (nums[m] == m) {
                left = left + 1;
            } else {
                right = m;
            }
        }
        return left;
    }

}
